package search;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class MajorityFind {

	/*
	 * This program finds whether a particular element is in majority i.e. this element must appear
	 * more than half of the times e.g. 51 out of 100 and not 50 out of 100 
	 * 
	 * if there is no majority, this method return null
	 * 
	 * Explanation of original linear-time majority vote algorithm:
	 * http://www.cs.utexas.edu/~moore/best-ideas/mjrty/
	 * 
	 * */
	public static String findMajority(List<String> listString){

		String candidate = "";
		String nextWord;

		int count = 0;
		int index = 0;
		int size = listString.size();

		while(index < size){
			nextWord = listString.get(index);
			if(count == 0){
				// if majority element exists, it'll get trapped here as its count++ is more than its count--
				candidate = nextWord; 
				count = 1;
			}else if(candidate.equalsIgnoreCase(nextWord)){
				count++;
			}else{
				count--;
			}
			index++;
		}

		// optimization
		if(count > size/2){
			return candidate;
		}

		// another O(n) scan in case majority element may not be in given input.
		// It can be avoided if assumption is that majority element has to be in the input 

		// variable to verify whether candidate is in majority
		int countMajority = 0;
		for (int i = 0; i < size; i++) {
			if (listString.get(i) == candidate) {
				countMajority++;
			}
			if (countMajority > size/2) {
				return candidate;
			}
		}
		
		// no majority element exists
		return null;
	}

	
	/*
	 * from http://www.americanscientist.org/issues/pub/the-britney-spears-problem/4
	 * 
	 * "Given a stream of length n, identify a set of size k that includes all the elements occurring
	 *  with a frequency greater than n /( k +1). (In the case of k =1, this reduces to the majority 
	 *  problem.)"
	 *  
	 *  "Again the results carry only a weak guarantee: If any elements of the stream exceed the 
	 *  threshold frequency, those elements will appear among the candidates, but not all the 
	 *  candidates are necessarily above the threshold. Even with this drawback, the algorithm performs 
	 *  impressive feats, such as scanning a stream of Web search queries for all terms that make up 
	 *  at least 1 percent of the traffic."
	 * 
	 *  Original paper of erik demaine:
	 *  http://erikdemaine.org/papers/NetworkStats_TR2002/paper.pdf
	 * 
	 * */
	public static List<String> findMajority(List<String> listString, int k){

		Map<String, Integer> wordSet = new TreeMap<String, Integer>();
		String word;

		Iterator<String> itr = listString.iterator();
		while(itr.hasNext()){
			word = itr.next();
		
			Integer count = wordSet.get(word);
			if(count == null){
				if(wordSet.size() == k){
					Iterator<Map.Entry<String, Integer>> itrMap = wordSet.entrySet().iterator();
					while(itrMap.hasNext()){
						Map.Entry<String, Integer> keyValuepair = itrMap.next();
						if(keyValuepair.getValue() == 1){
							itrMap.remove();
						}else{
							int currentValue = keyValuepair.getValue();
							wordSet.put(keyValuepair.getKey(), --currentValue);
						}
					}
				}else{
					wordSet.put(word, 1);
				}
			}else{
				int currentValue = wordSet.get(word);
				wordSet.put(word, ++currentValue);
			}
		}
		
		// case when all the entries removed in last iteration not handled
		
		// verify from the word whether frequency is greater than n/(k+1)
		int minFrequency = listString.size()/(k+1);
		List<String> listResult = new ArrayList<String>();
		Iterator<Map.Entry<String, Integer>> itrVerification = wordSet.entrySet().iterator();
		while(itrVerification.hasNext()){
			Map.Entry<String, Integer> keyValuepair = itrVerification.next();
			if(keyValuepair.getValue() >  minFrequency){
				listResult.add(keyValuepair.getKey());
			}
		}
		
		// approximate result
		return listResult;
	}

}


